The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan

摘要

We consider the problem of scheduling family jobs with release dates on a bounded batching machine to minimize the makespan. A polynomial-time approximation scheme for the identical job size model and an approximation algorithm with a worst-case ratio of 5/2 for the non-identical job size model will be derived.